home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / Moscow ML 1.42 / lib / Splaytree.sig < prev    next >
Encoding:
Text File  |  1997-08-18  |  754 b   |  25 lines  |  [TEXT/Moml]
  1. (* Splaytree -- Splay tree structure supporting Splaymap and Splayset.
  2.  * 
  3.  * Modified for Moscow ML from SML/NJ library which is 
  4.  * COPYRIGHT (c) 1993 by AT&T Bell Laboratories.  
  5.  * See file mosml/copyrght/copyrght.att for details.
  6.  *)
  7.  
  8. datatype 'a splay = 
  9.     SplayObj of {value : 'a,
  10.          right : 'a splay,
  11.          left  : 'a splay}
  12.   | SplayNil
  13.  
  14. val splay : ('a -> order) * 'a splay -> order * 'a splay
  15. val join  : 'a splay * 'a splay -> 'a splay
  16.  
  17. (* 
  18.    [splay (cmp,tree)] returns (r,tree') 
  19.    where tree' is tree adjusted using the comparison function cmp
  20.    and, if tree' = SplayObj{value,...}, then r = cmp value.
  21.    tree' = SplayNil iff tree = SplayNil, in which case r is undefined.
  22.  
  23.    [join(t,t')] returns a new splay tree formed of t and t'
  24. *)
  25.